package leetcode_800;

/**
 *@author 周杨
 *MinCostClimbingStairs_746 爬楼梯问题
 *describe:典型动态规划问题 AC 54%
 *2018年10月16日 下午1:12:59
 */
public class MinCostClimbingStairs_746 {
	/**
	 * describe:典型动态规划 AC 54%
	 * 2018年10月16日 下午1:08:00
	 */
	public int minCostClimbingStairs(int[] cost) {
        int dp[]=new int[cost.length+1];
        dp[0]=cost[0];
        dp[1]=cost[1];
        for(int i=2;i<cost.length;++i) {
        	dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i];
        }
        return Math.min(dp[cost.length-1], dp[cost.length-2]);
    }
	
	/**
	 * describe:优化后竟然只AC 48%
	 * 2018年10月16日 下午1:12:47
	 */
	public int minCostClimbingStairs1(int[] cost) {
        int pre=cost[0];
        int before=cost[1];
        int now;
        for(int i=2;i<cost.length;++i) {
        	now=Math.min(pre,before)+cost[i];
        	pre=before;
        	before=now;  	
        }
        return Math.min(before, pre);
    }
}
